//零钱兑换（medium）: https://leetcode.cn/problems/coin-change/
class Solution
{
public:
	int coinChange(vector<int>& coins, int amount)
	{
		// 1. 创建 dp 表
		// 2. 初始化
		// 3. 填表
		// 4. 返回值
		const int INF = 0x3f3f3f3f;
		int n = coins.size();
		vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
	
		for (int j = 1; j <= amount; j++)
		{
			dp[0][j] = INF;
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j <= amount; j++)
			{
				dp[i][j] = dp[i - 1][j];
				if (j >= coins[i - 1])
				{
					dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
				}
			}
		}
			
		return dp[n][amount] >= INF ? -1 : dp[n][amount];
	}
};

//零钱兑换II（medium）: https://leetcode.cn/problems/coin-change-ii/
class Solution
{
public:
	int change(int amount, vector<int>& coins)
	{
		vector<int> dp(amount + 1); // 建表
		dp[0] = 1; // 初始化
		for (auto x : coins) // 拿出物品
		{
			for (int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
			{
				dp[j] += dp[j - x];
			}
				
		}
			
		return dp[amount];
	}
};